package com.lw.leetcode.other.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 815. 公交路线
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/29 17:40
 */
public class NumBusesToDestination {


    public static void main(String[] args) {
        NumBusesToDestination test = new NumBusesToDestination();

        // 2
//        int[][] routes = {{1, 2, 7}, {3, 6, 7}};
//        int source = 1;
//        int target = 6;

        // -1
        int[][] routes = {{7, 12}, {4, 5, 15}, {6}, {15, 19}, {9, 12, 13}};
        int source = 15;
        int target = 12;

        int i = test.numBusesToDestination(routes, source, target);
        System.out.println(i);

    }


    public int numBusesToDestination(int[][] routes, int source, int target) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int length = routes.length;
        boolean w = false;
        boolean u = false;
        for (int i = 0; i < length; i++) {
            int[] route = routes[i];
            if (route.length == 1) {
                continue;
            }
            for (int r : route) {
                map.computeIfAbsent(r, v -> new ArrayList<>()).add(i);
                if (r == source) {
                    w = true;
                }
                if (r == target) {
                    u = true;
                }
            }
        }
        if (!(w && u)) {
            return -1;
        }
        if (source == target) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        int count = 1;
        set.add(source);
        List<Integer> items1 = new ArrayList<>();
        List<Integer> items2 = new ArrayList<>();
        items1.add(source);
        set.add(source);
        while (!items1.isEmpty()) {
            for (int k : items1) {
                List<Integer> list = map.get(k);
                if(list == null) {
                    continue;
                }
                for (int v : list) {
                    int[] route = routes[v];
                    for (int r : route) {
                        if (set.contains(r)) {
                            continue;
                        }
                        if (r == target) {
                            return count;
                        }
                        set.add(r);
                        items2.add(r);
                    }
                }
            }
            items1 = items2;
            items2 = new ArrayList<>();
            count++;
        }
        return -1;
    }

}
